#
# peerscape.db.db
#
# Copyright 2003-2009 Helsinki Institute for Information Technology
# and the authors.
#
# Authors: Ken Rimey <rimey@hiit.fi>
#

# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

# This file derives from db.py in PDIS (http://pdis.hiit.fi/).

"""
Sqlite3-based store for collections of signed key-value pairs

INTRODUCTION

This is the main Python API for application developers.  The following
is a quick overview of some of the methods of a DB instance (a
database handle).

First of all, opening a database requires specifying its location on
disk:

    from peerscape import DB
    db = DB(path_to_database=':memory:')

The database is created if it does not already exist.

DATASETS

The main content of the database is organized as shared datasets.
Each dataset has a unique information ID (IID), which is a string of
40 hexadecimal digits.

Datasets resemble file hierarchies.  Each dataset represents a
collection of key-value pairs, where the keys are paths and the values
are arbitrary byte strings.  A path is a sequence of one or more
non-empty strings, written using slash characters ('/') as separators.

Personal profiles are a special kind of dataset providing a unique
place to store information about a person or on-line persona -- or
more precisely, a principal (the party controlling a cryptographic
private key).  The IID of the profile can be computed from the
principal's public key and serves as an ID for the principal.

Group profiles are a second special kind of dataset, representing a
group of principals as defined by a membership list.  We refer to all
other datasets as content datasets.

IMPRINTING

Normally each database is imprinted with the persona of its owner.  At
most limited functionality will be available if it is not.

After creating a new database, a first-time user would normally call
init_persona() to create a new identity and imprint the database with it:

    db.init_persona(name) -> IID
    db.get_my_iid() -> IID
    db.get_persona() -> (IID, master secret)

The name can be changed freely later.  It is stored in the profile as
the value of "/info/title.txt".

A user who already has a personal profile (created at some other
computer) can instead imprint the database with it:

    db.set_persona(iid, secret)
    db.clear_persona()

The user's master secret is sensitive and cannot be reset, so
transporting it safely between computers is important.  Our solution
is to publish an encrypted version of it, protected by a
computer-generated code that the user can keep in his or her wallet.
The user can then fetch the master secret and imprint the database
with the persona by providing this code.

    db.init_recovery_code() -> string
    db.set_persona_from_code(code)

>>> db = DB()
>>> p = db.init_persona('Test Person')
>>> len(p)
40
>>> db.get_my_iid() == p
True
>>> db.get(p, '/info/title.txt')
'Test Person'

MANAGING DATASETS

After the database has been imprinted, it is possible to create new
groups or content datasets:

    db.create_group(name) -> IID
    db.create_dataset(title, type='unspecified') -> IID

One can query the type of a dataset:

    db.get_dataset_type(iid) -> unicode string

This method returns None if the answer is not known.  The dataset type
for a personal profile or group profile is "principal" or "group",
respectively.

One can also query what datasets are present in the database:

    db.list_datasets(type=None) -> list of IIDs

By default, this method lists all datasets of all types, as well as
datasets for which the type is not known.

The type of a dataset might not be known if the IID of a dataset that
was created elsewhere has been added to the database.  This is called
"subscribing" to a dataset.  It causes the synchronization agent to
try to fetch the contents of the dataset via the network.

    db.subscribe(iid)

Subscribing to a dataset automatically subscribes to additional
datasets as needed to verify the contents of the dataset.  This mainly
pertains to content datasets, which may depend on one or more personal
or group profiles through policy declarations (see the discussion of
Authorization below).

>>> g = db.create_group('Test Group')
>>> c = db.create_dataset('Test Content')

>>> db.get_dataset_type(p)
u'principal'
>>> db.get_dataset_type(g)
u'group'
>>> db.get_dataset_type(c)
u'unspecified'

>>> db.list_datasets(type='principal') == [p]
True
>>> db.list_datasets(type='group') == [g]
True
>>> db.list_datasets() == [p, g, c]
True

DATASET CONTENTS

The contents of a dataset consists of key-value pairs, where keys are
paths and values are arbitrary byte strings.  A path is a sequence of
one or more non-empty byte strings, which we ordinarily write using
the slash character ('/') as a separator.  We can think of the
elements of a path other than the last as naming folders.

    db.get(iid, path) -> value
    db.put(iid, path, value)

>>> db.put(c, '/data/color', 'red')
>>> db.get(c, '/data/color')
'red'

Slash-separated paths are unicode strings, the elements of which are
stored internally as UTF-8.  An arbitrary non-empty byte string can be
specified as a path element by writing it in hexadecimal with a prefix
of "0x".  This notation is also required for path elements that
contain slashes or start with "0x".

Although values are arbitrary byte strings, we provide convenience
methods for UTF-8 text values and JSON objects (JavaScript Object
Notation, http://json.org/).  It is also possible to fetch the size of
a value without fetching the value itself.

    db.get_text(iid, path) -> unicode
    db.get_json(iid, path) -> dict
    db.get_size(iid, path) -> integer
    db.get(iid, path, type=None) -> value

Specifying a type of 'text', 'json', or 'size' in the last method is
equivalent to calling one of the first three.  If the value is not
defined in the dataset, None is returned, except in the case of
get_size(), which raises LookupError.

>>> db.get_text(c, '/data/color')
u'red'
>>> db.get_size(c, '/data/color')
3

Values passed into put() are encoded using UTF-8 or JSON if they are
unicode or dictionaries, respectively.  Byte strings are stored as-is.

    db.put(iid, path, value)

>>> db.put(c, '/data/info.json', {'dimensions': [2, 4]})
>>> db.get_json(c, '/data/info.json')
{u'dimensions': [2, 4]}

The following methods allow for creation and updating of JSON objects
using convenient keyword argument syntax:

    db.put_json(iid, path, **kwargs)
    db.update_json(iid, path, **kwargs)

>>> db.update_json(c, '/data/info.json', shape='rectangular')
>>> db.get(c, '/data/info.json')
'{"dimensions": [2, 4], "shape": "rectangular"}'

It is often appropriate to keep people from overwriting each other's
data.  In such cases, we use a convention of including in the path the
hexadecimal IID of the person signing the update.  Intentional
overwriting can be prevented by granting write permission only for
paths that include the signer's IID in the appropriate position -- see
the discussion about authorization below.

For convenience, the methods of this API that accept paths replace any
path element that consists of a single exclamation point ("!") with
the IID of the owner of the database.

They do this using a helper method, parse_path(), which returns a list
of path elements.  It also accepts a list as input, in which case it
returns the list as-is.  This alternative list representation of paths
can thus be used to specify a path that literally includes the string
"!" as a path element.

    db.parse_path(path) -> list of byte strings

>>> path = '/data/comments/!/comment.txt'
>>> db.put(c, path, 'Cool!')
>>> db.get(c, path)
'Cool!'

>>> db.get(c, db.parse_path(path))
'Cool!'

It is possible to delete a value from the dataset:

    db.delete(iid, path)

This is accomplished in our distributed setting by creating an
invisible tombstone item for the path.

>>> db.delete(c, path)

One can query a dataset for all paths that begin with a particular
base path and have at least one more element than the base path:

    db.list(iid, base_path='') -> list of relative paths

The base path is removed from the head of each of the returned paths.
The results are returned in log order -- that is, according to when
the current value of the key was added to the database.

>>> db.list(c, '/data')
[u'color', u'info.json']

The list() method also enables monitoring a dataset for changes.  Each
time it is called, it saves the database's mark value (an integer) in
the DB instance.  This value can be fetched and passed into the next
query as last_mark to return only relative paths whose value has been
modified (set or deleted) since the previous query:

    db.list(iid, base_path='', last_mark=0) -> list of relative paths
    db.get_last_mark() -> integer

For convenience, we provide a way to access the contents of a folder
as a Python mapping, where the keys are paths relative to the folder.

    db.get_view(iid, base_path='', type=None) -> looks like a dict

Under the hood, operations on the view are implemented using the get,
put, delete, and list methods.

>>> v = db.get_view(c, '/data')
>>> v['color']
'red'
>>> v['color'] = 'blue'

SOCIAL NETWORKING

Personal profiles are linked together via symmetric friendships to
form a social network.  Group profiles and personal profiles are
linked via an asymmetric membership relationship.

    db.list_friends(person) -> list of person IIDs
    db.list_members(group) -> list of person IIDs

>>> db.list_friends(p) == []
True
>>> db.list_members(g) == [p]
True

Information about each relationship is stored as a JSON object in the
personal or group profile, under the key "/auth/<IID>".  For instance,
group members can be assigned named roles, which are stored in the
JSON object.

>>> info = db.get_json(g, '/auth/' + p)
>>> info['roles']
[u'admin']

Friendship and membership relationships are ordinarily created when
someone creates a single-use invitation code and passes it to someone
else, who accepts it.  Invitation codes are easy to write down or
type.  Each one must be kept secret and should not be revealed to any
third party.

    db.create_friendship_invitation_code() -> string

Anybody can create a friendship invitation code on their own behalf.
(A person's friends also have the ability to create friendship
invitation codes on behalf of that person, but this is not the normal
social practice.)

    db.create_membership_invitation_code(group, roles=[]) -> string

A membership invitation can optionally specify a list of named roles,
granting additional authority to the member.  These can include
"admin", "author", and user-defined roles -- see Authorization below.

Any member of a group can create membership invitation codes for that
group.  However, they can pass along only roles that they themselves
have been assigned, unless they have the role "admin".  The person who
creates a group is automatically an administrator (and also has
certain permanent rights as the creator of the group).

Someone receiving an invitation code can destructively retrieve the
corresponding invitation object, subscribe to and view the pertinent
profile, consider the source of the invitation code, and then, at his
discretion, accept the invitation:

    db.fetch_invitation(code) -> invitation instance
    invitation.iid
    invitation.accept(db)

Invitations that are not retrieved within one week expire and
disappear from the system.

Either party to a friendship can cancel it as follows:

    db.cancel_friendship(person)

Either an administrator or the member in question can cancel a
membership as follows:

    db.cancel_membership(group, person)

The roles assigned to a group member can easily be updated by an
administrator of the group, using the update_json() method.

>>> db.update_json(g, '/auth/' + p, roles=['admin', 'superhero'])

AUTHORIZATION

Which of the above operations are permitted and which will raise an
exception ("Unauthorized") depends on the dataset and who is
performing the operation.

The creator of a dataset has unrestricted rights to update its
contents.  Policy declarations can be added to the dataset to allow
other principals to update some portion of the contents.

New personal and group profiles include certain standard policy
declarations.  These grant friends/members limited rights to manage
relationships, as outlined above.  They also give group administrators
unrestricted rights to update the contents of the group profile.

Unless the creator of a content dataset decides otherwise, he is the
only one who can write to the dataset.  The add_signing_policy() method
can be used to add a policy declaration to permit others to do so:

    db.add_signing_policy(iid, '*', pattern)
    db.add_signing_policy(iid, group, pattern, roles=None)
    db.add_signing_policy(iid, person, pattern, roles=None)
    db.clear_signing_policy(iid, who, pattern)

In the first case above, the signing rights are granted to anyone and
everyone.  In the second case, they are granted to the members of the
specified group, possibly restricted to those members who have one of
a specified set of roles.  In the third case, they are granted to the
specified person and his friends.  However, if roles=['admin'] is
specified, the signing rights are granted only to the person himself.

The pattern determines which paths those people are permitted to
update (create, modify, or delete).  A pattern is matched against a
path element-by-element.  "*" matches an arbitrary element.  "!"
matches the hexadecimal IID of the person signing the update.  "..."
matches all the remaining elements of the path, of which there must be
at least one.  Any other string matches only an identical element.

Because policy declarations are stored in the dataset itself (in the
folder "/policy"), granting unrestricted signing rights to the dataset
delegates rights management rights.  For instance, the following
allows the administrators of a specified group to manage the dataset:

    db.add_signing_policy(iid, group, '/...', roles=['admin'])

>>> db.close()
"""

from __future__ import with_statement

import os
import hmac
from hashlib import sha1
from binascii import hexlify, unhexlify

from peerscape.lib import json
from peerscape.lib.cipher import Cipher
from peerscape.lib.sexp import encode, decode
from peerscape.core.identity import generate, decode_identity
from peerscape.core.item import (
    create_root_item, create_kv_item, RootItem,
    root_item_from_sqlite, kv_item_from_sqlite)
from peerscape.core.policy import verify, Unauthorized
from peerscape.core.path import path_to_list, list_to_path, decode_text
from peerscape.core.iid import is_canonical_iid, hex, hex_to_buffer

if 'APSW' in os.environ:
    from peerscape.db.apsw_db import SqliteDB, IntegrityError
else:
    from peerscape.db.sqlite_db import SqliteDB, IntegrityError

from peerscape.db.cursor import get_single_row, get_single_value, get_values
from peerscape.db.node_id import get_node_id
from peerscape.db.view import View
from peerscape.db.escrow import get_escrow
from peerscape.db.invitation import generate_code, strengthen
from peerscape.db.util import *

INFO_TABLE = """
create table if not exists info(
    k primary key,
    v)"""

DATASETS_KEYS = ('num', 'iid', 'type', 'salt', 'sig', 'pk', 'info', 'size')

DATASETS_TABLE = """
create table if not exists datasets(
    num integer primary key autoincrement,
    iid unique,
    type,
    salt,
    sig,
    pk,
    info,
    size integer default 0)"""

ITEMS_KEYS = ('num', 'hash', 'iid', 'key', 'value', 'seq',
             'sig', 'pk', 'sig2', 'pk2', 'size')

ITEMS_TABLE = """
create table if not exists items(
    num integer primary key autoincrement,
    hash unique,
    iid,
    key,
    value,
    seq integer,
    sig,
    pk,
    sig2,
    pk2,
    size integer)"""

ITEMS_BY_NUM = """
create index if not exists items_by_num on items(iid, num)"""

ITEMS_BY_KEY = """
create index if not exists items_by_key on items(iid, key, num)"""

def init_doctest():
    """Initialize variables referred to in the doctests."""
    global identity0, identity1, identity2, identity3
    identity0 = generate(size=512)
    identity1 = generate(size=512)
    identity2 = generate(size=512)
    identity3 = generate(size=512)

_undefined = object()

class CoreDB(SqliteDB):
    """
    Database Instance
    """
    initialization = [INFO_TABLE, DATASETS_TABLE,
                      ITEMS_TABLE, ITEMS_BY_NUM, ITEMS_BY_KEY]

    def __init__(self, path=':memory:', cache_persona=False, **kwargs):
        """
        Initialize the database handle.

         * path -- location of database on disk.  Can use "~" notation.

         * create -- whether to create the database file if it does
           not exist.  Setting this to False is recommended when
           repeatedly creating short-lived database handles.

         * timeout -- how long to wait before raising an exception
           signalling "database is locked".

         * cache_persona -- whether to cache the user's IID and master
           secret in the database handle after fetching them from the
           database for the first time.  The cached persona is not
           updated if the persona imprinted in the database changes,
           so please do not enable this optimization for long-lived
           database handles.
        """
        SqliteDB.__init__(self, path, **kwargs)
        self.my_id = get_node_id(self.path)
        self.cache_persona = cache_persona
        self.persona = None
        self.last_mark = None # database mark at the time of the last query

    #
    # System information
    #

    def get_disk_usage(self):
        """Return the size of the database in bytes."""
        return os.path.getsize(self.path)

    #
    # Database info table
    #

    def get_local_info(self, key, default=_undefined):
        c = self.execute("select v from info where k = ?", (key,))
        try:
            value = get_single_value(c)
            return str(value) if isinstance(value, buffer) else value
        except LookupError:
            if default != _undefined:
                return default
            else:
                raise

    def set_local_info(self, key, value):
        value = buffer(value) if isinstance(value, str) else value
        self.operate("replace into info values (?, ?)", (key, value))

    def clear_local_info(self, key):
        self.operate("delete from info where k = ?", (key,))

    def _test_local_info(self):
        """
        >>> db = DB()
        >>> db.set_local_info('answer', 42)

        >>> db.set_local_info('color', 'red')
        >>> db.get_local_info('color')
        'red'
        >>> db.set_local_info('color', u'green')
        >>> db.get_local_info('color')
        u'green'
        >>> db.clear_local_info('color')
        >>> db.get_local_info('color')
        Traceback (most recent call last):
            ...
        LookupError

        >>> db.get_local_info('answer', 99)
        42
        >>> db.get_local_info('nonexistent', 99)
        99
        >>> db.close()
        """
        pass

    #
    # Derived secrets
    #

    def get_cipher(self, reference, purpose, master_secret=None):
        return Cipher(self.get_secret(reference, purpose, master_secret))

    def get_secret(self, reference, purpose, master_secret=None):
        reference = hex(reference)
        secret = master_secret or self.get_my_master_secret()
        return hmac.new(secret, reference + '\x00' + purpose, sha1).digest()

    def _test_derived_secrets(self):
        """
        >>> db = DB()
        >>> me = db.init_persona(_identity=identity0)
        >>> other = buffer(os.urandom(20))
        >>> s1 = db.get_secret(me, 'this')
        >>> s2 = db.get_secret(me, 'that')
        >>> s3 = db.get_secret(other, 'this')
        >>> s4 = db.get_secret(other, 'that')
        >>> secrets = [s1, s2, s3, s4]
        >>> map(len, secrets)
        [20, 20, 20, 20]
        >>> len(set(secrets))   # distinct
        4

        >>> cipher = db.get_cipher(me, 'test')
        >>> ciphertext = cipher.encrypt('Testing...')
        >>> len(ciphertext)
        32
        >>> cipher.decrypt(ciphertext)
        'Testing...'
        >>> db.close()
        """
        pass

    #
    # Group secret -- secret shared by friends or members.
    #

    def get_group_cipher(self, iid):
        """Return the cipher shared by the friends/members of a principal/group."""
        return Cipher(self.get_group_secret(iid))

    def get_group_secret(self, iid, my_iid=None, my_master_secret=None):
        """Return the secret shared by the friends/members of a principal/group."""
        iid = hex(iid)
        with self.read_transaction():
            my_iid = my_iid or self.get_my_iid()
            info = self.get_json(iid, ['auth', my_iid])
            if info and 'secret' in info:
                secret = info['secret']
                salt = info.get('salt', iid)
                return self.decrypt_group_secret(secret, salt, my_master_secret)
            else:
                raise LookupError

    def encrypt_group_secret(self, secret, salt, master_secret=None):
        cipher = self.get_cipher(salt, 'encrypt group secret', master_secret)
        return hexlify(cipher.encrypt(secret))

    def decrypt_group_secret(self, secret, salt, master_secret=None):
        cipher = self.get_cipher(salt, 'encrypt group secret', master_secret)
        secret = unhexlify(secret)    # Can raise TypeError.
        return cipher.decrypt(secret) # Can raise ValueError.

    def _test_group_secret(self):
        """
        >>> db = DB()
        >>> me = db.init_persona(_identity=identity0)
        >>> group = db.create_group()

        >>> db2 = DB()
        >>> me2 = db2.init_persona(_identity=identity2)
        >>> group2 = db2.create_group()

        >>> len(db.get_group_secret(me))
        20
        >>> len(db.get_group_secret(group))
        20

        >>> db.get_group_secret(me2)
        Traceback (most recent call last):
            ...
        LookupError
        >>> sync(db2, db)
        >>> db.get_group_secret(me2)
        Traceback (most recent call last):
            ...
        LookupError

        >>> i = db2._create_friendship_invitation()
        >>> i.accept(db)
        'OK'
        >>> sync(db, db2)
        >>> db.get_group_secret(me) == db2.get_group_secret(me)
        True
        >>> db.get_group_secret(me2) == db2.get_group_secret(me2)
        True

        >>> db.close()
        >>> db2.close()
        """
        pass

    #
    # Private key
    #

    def get_private_key(self, iid=None, master_secret=None):
        with self.read_transaction():
            iid = iid or self.get_my_iid()
            cipher = self.get_cipher(iid, 'encrypt private key', master_secret)
            sexp = self.get(iid, '/admin/private_key', cipher=cipher)
            if sexp:
                return decode_identity(sexp)
            else:
                raise LookupError('Private key not available.')

    def set_private_key(self, identity, iid, master_secret):
        cipher = self.get_cipher(iid, 'encrypt private key', master_secret)
        self.put(iid, '/admin/private_key', identity.encode_private(),
                 cipher=cipher, identity=identity)

    def _test_private_key(self):
        """
        >>> db = DB()
        >>> db.get_private_key()
        Traceback (most recent call last):
            ...
        LookupError
        >>> me = db.init_persona(_identity=identity0)
        >>> identity = db.get_private_key()
        >>> identity.has_private()
        True
        >>> identity.digest() == identity0.digest()
        True
        >>> db.close()
        """
        pass

    #
    # My persona
    #

    def get_my_iid(self):
        """Return the user's IID."""
        return self.get_persona()[0]

    def get_my_master_secret(self):
        """Return the user's master secret."""
        return self.get_persona()[1]

    def get_persona(self):
        """Return the user's IID and master secret."""
        if self.persona:
            return self.persona

        with self.read_transaction():
            iid = self.get_local_info('my_iid')
            secret = self.get_local_info('my_secret')

        if self.cache_persona:
            self.persona = iid, secret

        return iid, secret

    def init_persona(self, name=u'', _identity=None):
        """Create a new principal and imprint the database it."""
        identity = _identity or generate() # outside the transaction
        with self.write_transaction():
            if self.get_local_info('my_iid', None):
                raise Unauthorized('Persona already initialized.')
            iid, master_secret = self.create_principal(name, identity)
            self.set_persona(iid, master_secret)
            return iid

    def clear_persona(self):
        """Prepare to imprint the database with a different persona."""
        if self.cache_persona:
            self.persona = None
        else:
            assert not self.persona

        with self.write_transaction():
            self.clear_local_info('my_iid')
            self.clear_local_info('my_secret')

    def set_persona(self, iid, secret):
        """Imprint the database with a persona."""
        iid = hex(iid)
        assert len(iid) == 40
        assert len(secret) == 20

        if self.cache_persona:
            self.persona = None
        else:
            assert not self.persona

        with self.write_transaction():
            if self.get_local_info('my_iid', None):
                raise Unauthorized('Persona already initialized.')
            self.subscribe(iid)
            self.set_local_info('my_iid', iid)
            self.set_local_info('my_secret', secret)

    def use_persona(self, iid, secret):
        """
        Specify a persona for operations performed using this DB instance only.

        This method enables provides for access to the datastore using
        a particular persona independently of the personas used by
        other database handles (DB instances) and without regard for
        any persona imprinted in the database.
        """
        assert not self.cache_persona
        self.persona = iid, secret

    def _test_persona(self):
        """
        >>> db = DB()

        >>> iid = db.init_persona('Test User', _identity=identity1)
        >>> db.get_dataset_type(iid)
        u'principal'
        >>> db.get_text(iid, '/info/title.txt')
        u'Test User'
        >>> db.init_persona(_identity=identity2)
        Traceback (most recent call last):
            ...
        Unauthorized: Persona already initialized.

        >>> secret = db.get_my_master_secret()
        >>> db.get_my_iid() == iid
        True
        >>> db.get_persona() == (iid, secret)
        True

        >>> db.clear_persona()
        >>> db.get_persona()
        Traceback (most recent call last):
            ...
        LookupError
        >>> db.set_persona(iid, secret)
        >>> db.get_persona() == (iid, secret)
        True

        >>> db.clear_persona()
        >>> db.use_persona(iid, secret)
        >>> db.get_persona() == (iid, secret)
        True

        >>> db.close()

        >>> db = DB(cache_persona=True)
        >>> iid = db.init_persona('Test User', _identity=identity1)
        >>> secret = db.get_my_master_secret()
        >>> db.get_persona() == (iid, secret)
        True
        >>> db.persona == (iid, secret)
        True
        >>> db.close()
        """
        pass

    #
    # Key escrow
    #

    def init_recovery_code(self, passphrase=u''):
        """Establish and return a new recovery code."""
        code = generate_code(20)
        key = self.calculate_escrow_key(code, passphrase)
        encryption_key = hmac.new(key, 'encryption key', sha1).digest()

        info = {'key': hexlify(key),
                'code': code,
                'passphrase': passphrase}
        n = len(json.dumps(passphrase))
        if n < 100:
            info['padding'] = 'x' * (100 - n)

        with self.write_transaction():
            iid, secret = self.get_persona()
            self.set_escrow_info(iid, info)
            self.put(iid, '/admin/escrow/master_secret', secret,
                     cipher=Cipher(encryption_key))

        return code

    def set_persona_from_code(self, code, passphrase=u''):
        """
        Imprint the database using a recovery code.

        This first looks for the escrowed persona in the local
        database, and then in OpenLookup.

        It raises LookupError if no escrowed information is found.
        It can also raise lookup.Error.
        """
        iid, secret = self.recover_persona(code, passphrase)
        self.set_persona(iid, secret)

    def recover_persona(self, code, passphrase=u''):
        key = self.calculate_escrow_key(code, passphrase)

        for iid in self.list_datasets(type='principal'):
            try:
                secret = self.recover_master_secret(iid, key)
                return iid, secret
            except LookupError:
                continue

        return get_escrow(key)

    def recover_master_secret(self, iid, key):
        encryption_key = hmac.new(key, 'encryption key', sha1).digest()
        try:
            secret = self.get(iid, '/admin/escrow/master_secret',
                              cipher=Cipher(encryption_key))
        except Exception:
            raise LookupError('Could not decrypt master secret in profile.')

        if not secret:
            raise LookupError('No escrowed master secret in profile.')

        return secret

    def calculate_escrow_key(self, code, passphrase):
        code = str(code)        # in case it's unicode
        return strengthen(code + '\x00' + passphrase.encode('utf-8'),
                          salt='-key-escrow')

    def get_escrow_info(self, iid):
        cipher=self.get_cipher(iid, 'encrypt escrow keys')
        return self.get_json(iid, '/admin/escrow/escrow_keys', cipher=cipher)

    def set_escrow_info(self, iid, info):
        cipher=self.get_cipher(iid, 'encrypt escrow keys')
        self.put(iid, '/admin/escrow/escrow_keys', info, cipher=cipher)

    def _test_key_escrow(self):
        """
        >>> db = DB()
        >>> iid = db.init_persona(_identity=identity0)
        >>> code = db.init_recovery_code('This is a test...')

        >>> db2 = DB()
        >>> sync(db, db2)
        >>> db2.set_persona_from_code(code, 'This is a test...')

        >>> db.get_persona() == db2.get_persona()
        True
        >>> db2.get_escrow_info(iid)['passphrase']
        u'This is a test...'

        >>> db.close()
        >>> db2.close()
        """
        pass

    #
    # Creating datasets
    #

    def create_dataset(self, title=u'', type='unspecified', identity=None):
        """Create a new dataset and return its IID."""
        with self.write_transaction():
            identity = identity or self.get_private_key()
            root = create_root_item(identity, type)
            iid = hexlify(root.iid)
            self.subscribe(iid)
            self.put_item(root)
            self.put(iid, '/info/title.txt', title, identity=identity)
            self.update_timestamp(iid, '/info/created', identity=identity)
            self.update_timestamp(iid, '/info/modified', identity=identity)
            return iid

    def create_group(self, name=u''):
        """Create a new group and return its IID."""
        group_secret = os.urandom(20)
        with self.write_transaction():
            my_iid = self.get_my_iid()
            my_name = self.get_text(my_iid, '/info/title.txt') or u''

            iid = self.create_dataset(name, 'group')
            info = dict(roles=['admin'], name=my_name,
                        secret=self.encrypt_group_secret(group_secret, iid))
            self.put(iid, ['auth', my_iid], info)
            self.put(iid, ['info', 'secret'], sha1(group_secret).digest())

            self.add_signing_policy(iid, '!', '/...', roles=['admin'])
            self.add_signing_policy(iid, '!', '/auth/!')
            self.add_signing_policy(iid, '!', '/restricted/link/*',
                                    roles=['author'])
            self.add_signing_policy(iid, '!', '/info/modified')
            self.add_signing_policy(iid, '!', '/public/event.json')
            self.add_signing_policy(iid, '!', '/restricted/event.json')
            self.update_timestamp(iid)
            return iid

    def create_principal(self, name=u'', _identity=None):
        identity = _identity or generate()
        master_secret = os.urandom(20)
        with self.write_transaction():
            iid = self.create_dataset(name, 'principal', identity=identity)
            self.set_private_key(identity, iid, master_secret)

            secret = self.get_secret(iid, 'my group secret', master_secret)
            info = dict(roles=['admin'],
                        secret=self.encrypt_group_secret(secret, iid,
                                                         master_secret))
            self.put(iid, ['auth', iid], info, identity=identity)
            self.put(iid, ['info', 'secret'], sha1(secret).digest(),
                     identity=identity)

            for pattern in ['/auth/!',
                            '/info/modified',
                            '/public/event.json',
                            '/restricted/event.json']:
                self.add_signing_policy(iid, '!', pattern, identity=identity)

            self.add_signing_policy(iid, '*', '/inbox/!', identity=identity)

            self.update_timestamp(iid, identity=identity)

            return iid, master_secret

    def _test_create_dataset(self):
        """
        >>> db = DB()
        >>> me = db.init_persona(_identity=identity1)
        >>> iid = db.create_dataset('Test Dataset')
        >>> db.get_text(iid, '/info/title.txt')
        u'Test Dataset'
        >>> db.get_dataset_type(iid)
        u'unspecified'
        >>> db.close()
        """
        pass

    def _test_create_group(self):
        """
        >>> db = DB()
        >>> me = db.init_persona('Me', _identity=identity1)
        >>> group = db.create_group('Test Group')
        >>> db.get_text(group, '/info/title.txt')
        u'Test Group'
        >>> db.get_dataset_type(group)
        u'group'
        >>> db.list_members(group) == [me]
        True
        >>> db.get_json(group, ['auth', me])['roles']
        [u'admin']
        >>> db.get_json(group, ['auth', me])['name']
        u'Me'
        >>> len(db.get_group_secret(group))
        20

        >>> db2 = DB()
        >>> joe = db2.init_persona('Joe', _identity=identity2)
        >>> db.put_json(group, ['auth', joe], roles=['loser'])
        >>> sync(db, db2)
        >>> db2.put_json(group, ['auth', joe], roles=[])
        >>> db2.put_json(group, ['auth', joe], roles=['winner'])
        Traceback (most recent call last):
            ...
        Unauthorized

        >>> sync(db2, db)
        >>> db.put_json(group, ['auth', joe], roles=['admin'])
        >>> sync(db, db2)
        >>> db2.delete(group, ['auth', me])
        >>> db2.put_json(group, ['auth', joe], roles=['winner'])

        >>> db.close()
        >>> db2.close()
        """
        pass

    def _test_create_principal(self):
        """
        >>> db = DB()
        >>> p, s = db.create_principal('Person 1', _identity=identity1)
        >>> db.get_dataset_type(p)
        u'principal'
        >>> db.get_private_key(p, s).digest() == identity1.digest()
        True
        >>> expected = db.get_secret(p, 'my group secret', s)
        >>> db.get_group_secret(p, p, s) == expected
        True
        >>> db.get_json(p, ['auth', p])['roles']
        [u'admin']
        >>> db.close()
        """
        pass

    #
    # Listing datasets
    #

    def get_dataset_type(self, iid):
        """Return the type of a dataset or None if we have no data."""
        iid = hex_to_buffer(iid)
        c = self.execute("select type from datasets"
                         " where iid = ?", (iid,))
        try:
            return get_single_value(c) # Can be None.
        except LookupError:
            return None

    def get_dataset_creator(self, iid):
        """Return the IID of the person that created a dataset."""
        try:
            identity = self.get_dataset_creator_public_key(iid)
        except LookupError:
            return None

        root = RootItem(identity.digest(), type='principal')
        return hexlify(root.hash)

    def get_dataset_creator_public_key(self, iid):
        """
        Return the public key of the dataset creator as an Identity instance.

        LookupError is raised if the information is not available.
        """
        iid = hex_to_buffer(iid)
        c = self.execute("select pk from datasets"
                         " where iid = ?", (iid,))
        try:
            pk = get_single_value(c)
        except LookupError:
            raise LookupError('No subscription.')

        if pk is None:
            raise LookupError('No root.')

        return decode_identity(str(pk))

    def list_datasets(self, type=None):
        """List the IIDs of the datasets to which we are subscribed."""
        if type is None:
            c = self.execute("select iid from datasets")
        else:
            c = self.execute("select iid from datasets"
                             " where type = ?", (type,))
        return map(hexlify, get_values(c))

    def list_datasets_by_prefix(self, prefix):
        """List the dataset IIDs that start with a specified prefix."""
        prefix = hex(prefix).upper()
        c = self.execute("select iid from datasets"
                         " where ? = substr(hex(iid), 1, ?)",
                         (prefix, len(prefix)))
        return map(hexlify, get_values(c))

    def _test_listing_datasets(self):
        """
        >>> db = DB()

        >>> person = db.init_persona(_identity=identity0)
        >>> group = db.create_group()
        >>> content = db.create_dataset(type='content')
        >>> subscribed = '1234abcd' * 5; db.subscribe(subscribed)
        >>> other = '87654321' * 5
        >>> iids = [person, group, content, subscribed, other]

        >>> [db.get_dataset_type(iid) for iid in iids]
        [u'principal', u'group', u'content', None, None]

        >>> [db.get_dataset_creator(iid) for iid in iids] == [
        ...     person, person, person, None, None]
        True

        >>> db.list_datasets() == [person, group, content, subscribed]
        True
        >>> db.list_datasets(type='principal') == [person]
        True
        >>> db.list_datasets(type='group') == [group]
        True
        >>> db.list_datasets(type='content') == [content]
        True

        >>> db.list_datasets_by_prefix(content[:10]) == [content]
        True
        >>> db.list_datasets_by_prefix('') == db.list_datasets()
        True
        >>> db.list_datasets_by_prefix(buffer(os.urandom(10))) == []
        True

        >>> db.close()
        """
        pass

    #
    # Dataset info -- extensible property list.
    #

    def get_dataset_info(self, iid):
        """Return a dictionary with information about a subscribed dataset."""
        iid = hex_to_buffer(iid)
        c = self.execute("select type, size, info from datasets"
                         " where iid = ?", (iid,))
        try:
            type, size, info = get_single_row(c)
        except LookupError:
            return None

        info = json.loads(info)
        info[u'size'] = size
        if type:
            info[u'type'] = type

        return info

    def set_dataset_info(self, iid, info):
        # This simply has no effect if the subscription does not exist.
        iid = hex_to_buffer(iid)
        info.pop('type', None)
        info.pop('size', None)
        info = json.dumps(info, sort_keys=True)
        self.operate("update datasets set info = ?"
                     " where iid = ?", (info, iid))

    def update_dataset_info(self, iid, **kwargs):
        with self.write_transaction():
            info = self.get_dataset_info(iid)
            if info is not None:
                info.update(kwargs)
                self.set_dataset_info(iid, info)

    def touch(self, iid):
        # XXX Use an in-memory hash table to throttle these to one per
        # minute per dataset.
        self.update_dataset_info(iid, touched=get_timestamp())

    def _test_get_dataset_info(self):
        """
        >>> db = DB()

        >>> person = db.init_persona(_identity=identity0)
        >>> info = db.get_dataset_info(person)
        >>> sorted(info.keys())
        [u'size', u'touched', u'type']
        >>> info['type']
        u'principal'
        >>> info['size'] > 0
        True

        >>> iid = db.create_dataset()
        >>> info = db.get_dataset_info(iid)
        >>> sorted(info.keys())
        [u'size', u'touched', u'type']
        >>> info['type']
        u'unspecified'
        >>> info['size'] > 0
        True

        >>> unknown = '1234abcd' * 5
        >>> db.get_dataset_info(unknown) is None
        True

        >>> db.subscribe(unknown)
        >>> info = db.get_dataset_info(unknown)
        >>> sorted(info.keys())
        [u'size', u'touched']
        >>> info['size']
        0

        >>> db.close()
        """
        pass

    def _test_set_dataset_info(self):
        """
        >>> db = DB()
        >>> me = db.init_persona(_identity=identity0)
        >>> iid1 = db.create_dataset()
        >>> iid2 = db.create_dataset()
        >>> unknown = '1234abcd' * 5
        >>> db.set_dataset_info(iid1, {'size':-1, 'color': 'red'})
        >>> db.set_dataset_info(iid2, {'size':-1, 'color': 'blue'})
        >>> db.set_dataset_info(unknown, {'size':-1, 'color': 'green'})
        >>> db.get_dataset_info(iid1)['color']
        u'red'
        >>> db.get_dataset_info(iid2)['color']
        u'blue'
        >>> db.get_dataset_info(iid1)['size'] > 0
        True
        >>> db.get_dataset_info(iid2)['size'] > 0
        True
        >>> db.get_dataset_info(unknown) is None
        True
        >>> db.close()
        """
        pass

    def _test_update_dataset_info(self):
        """
        >>> db = DB()

        >>> iid = db.init_persona(_identity=identity0)
        >>> db.update_dataset_info(iid, color='red', shape='round')
        >>> db.update_dataset_info(iid, shape='square', name='test')
        >>> info = db.get_dataset_info(iid)
        >>> info['color']
        u'red'
        >>> info['shape']
        u'square'
        >>> info['name']
        u'test'

        >>> unknown = '1234abcd' * 5
        >>> db.update_dataset_info(unknown, color='blue')
        >>> db.get_dataset_info(unknown) is None
        True

        >>> db.close()
        """
        pass

    def _test_touch(self):
        """
        >>> db = DB()
        >>> iid = '1234abcd' * 5
        >>> db.subscribe(iid)
        >>> info = db.get_dataset_info(iid)
        >>> len(info['touched']) == len('yyyy-mm-ddThh:mm:ss')
        True
        >>> db.set_dataset_info(iid, {})
        >>> 'touched' in db.get_dataset_info(iid)
        False
        >>> db.touch(iid)
        >>> info = db.get_dataset_info(iid)
        >>> len(info['touched']) == len('yyyy-mm-ddThh:mm:ss')
        True
        >>> db.close()
        """
        pass

    #
    # Subscribe
    #

    def subscribe(self, iid):
        """Subscribe to a dataset."""
        iid = hex_to_buffer(iid)
        assert len(iid) == 20

        info = json.dumps({'touched': get_timestamp()})
        try:
            self.operate("insert into datasets (iid, info)"
                         " values (?, ?)", (iid, info))
        except IntegrityError:
            pass                # Already there.

    def _test_subscribe(self):
        """
        >>> db = DB()
        >>> me = db.init_persona(_identity=identity0)
        >>> iid1 = db.create_dataset()
        >>> iid2 = '1234abcd' * 5
        >>> db.subscribe(iid1)
        >>> db.subscribe(iid2)
        >>> db.subscribe(iid2)
        >>> db.list_datasets() == [me, iid1, iid2]
        True
        >>> info = db.get_dataset_info(iid2)
        >>> len(info['touched']) == len('yyyy-mm-ddThh:mm:ss')
        True
        >>> db.close()
        """
        pass

    #
    # Managing relationships
    #

    def list_friends(self, person):
        """List the IIDs of a person's friends."""
        iids = self.list(person, '/auth')
        if person in iids:
            iids.remove(person)
        return [iid for iid in iids if is_canonical_iid(iid)]

    def list_members(self, group):
        """List the IIDs of the members of a group."""
        iids = self.list(group, '/auth')
        return [iid for iid in iids if is_canonical_iid(iid)]

    def members(self, group):
        """
        Return a view mapping member IIDs to member info for a group.

        Usage:
            if person in db.members(group): ...
            for person in db.members(group): ...
            for person, info in db.members(group).items(): ...

        The argument can also refer to a person, in which case the
        view includes the person's friends and the person himself.
        """
        return self.get_view(group, '/auth', type='json')

    def cancel_friendship(self, person):
        """Cancel a friendship between the user and another person."""
        person = hex(person)
        with self.write_transaction():
            my_iid = self.get_my_iid()
            self.delete(my_iid, ['auth', person])
            self.delete(person, ['auth', my_iid])

    def cancel_membership(self, group, person):
        """Remove a member from a group."""
        person = hex(person)
        with self.write_transaction():
            self.delete(group, ['auth', person])

    def _test_relationships(self):
        """
        >>> db = DB()
        >>> db2 = DB()
        >>> p1 = db.init_persona('Person 1', _identity=identity1)
        >>> p2 = db2.init_persona('Person 2', _identity=identity2)

        >>> i = db2._create_friendship_invitation()
        >>> sync(db2, db)
        >>> i.accept(db)
        'OK'
        >>> db.list_friends(p1) == [p2]
        True
        >>> db.list_friends(p2) == [p1]
        True

        >>> v = db.members(p1)
        >>> v.keys() == [p1, p2]
        True

        >>> db.cancel_friendship(p2)
        >>> db.list_friends(p1) == []
        True
        >>> db.list_friends(p2) == []
        True

        >>> g = db2.create_group('Test Group')
        >>> i = db2._create_membership_invitation(g)
        >>> sync(db2, db)
        >>> i.accept(db)
        'OK'
        >>> db.list_members(g) == [p2, p1]
        True

        >>> v = db.members(g)
        >>> v.keys() == [p2, p1]
        True
        >>> v[p2]['roles']
        [u'admin']

        >>> db.cancel_membership(g, p1)
        >>> db.list_members(g) == [p2]
        True

        >>> db.close()
        >>> db2.close()
        """
        pass

    #
    # Message inbox (mainly only for invitations -- see invitation.py).
    #

    def leave_message(self, iid, data, sender_iid=None):
        """
        Store a private message in the recipient's personal profile.

        The message data must be a dictionary of byte strings.  Any
        existing message from the same sender is overwritten.
        """
        data = sorted(data.items())
        for k, v in data:
            assert isinstance(k, str)
            assert isinstance(v, str)

        encryption_key = os.urandom(16)
        plaintext = encode(['message'] + data)
        ciphertext = Cipher(encryption_key).encrypt(plaintext)

        with self.write_transaction():
            assert self.get_dataset_type(iid) == 'principal'
            sender_iid = sender_iid or self.get_my_iid()
            identity = self.get_dataset_creator_public_key(iid)
            payload = ['rsa-aes', identity.encrypt(encryption_key), ciphertext]
            self.put(iid, ['inbox', hex(sender_iid)], encode(payload))

    def is_message_pending(self, iid, sender_iid=None):
        """
        Test whether the message has yet to be cleared.

        This works even if the message contents are indecipherable.
        """
        with self.read_transaction():
            sender_iid = sender_iid or self.get_my_iid()
            value = self.get(iid, ['inbox', hex(sender_iid)])
            return value is not None

    def list_messages(self, iid=None):
        """
        Return a list of sender IIDs for private messages.

        The IIDs will be in log order with the most recent message last.
        """
        with self.read_transaction():
            iid = iid or self.get_my_iid()
            return self.list(iid, '/inbox')

    def read_message(self, sender_iid):
        """
        Return the message data from a particular sender.

        LookupError is raised if there is no message.  (ValueError may
        also be raised under various exceptional circumstances.)
        """
        with self.read_transaction():
            my_iid = self.get_my_iid()
            value = self.get(my_iid, ['inbox', hex(sender_iid)])
            if value is None:
                raise LookupError('No such message.')

            head, encryption_key, ciphertext = decode(value)
            if head != 'rsa-aes':
                raise ValueError('Unknown message encryption algorithm.')

            identity = self.get_private_key(my_iid)
            encryption_key = identity.decrypt(encryption_key)
            plaintext = Cipher(encryption_key).decrypt(ciphertext)

            data = decode(plaintext)
            if data.pop(0) != 'message':
                raise ValueError('Bad message.')
            return dict(data)

    def clear_message(self, sender_iid, iid=None):
        """
        Delete any message from the specified sender.
        """
        with self.write_transaction():
            iid = iid or self.get_my_iid()
            self.delete(iid, ['inbox', hex(sender_iid)])

    def _test_message_inbox(self):
        """
        >>> db = DB()
        >>> p1, s1 = db.create_principal('User 1', _identity=identity1)
        >>> p2, s2 = db.create_principal('User 2', _identity=identity2)

        >>> data = dict(color='blue', shape='round')

        >>> db.use_persona(p1, s1)
        >>> db.is_message_pending(p2)
        False
        >>> db.leave_message(p2, data)
        >>> db.is_message_pending(p2)
        True

        >>> db.use_persona(p2, s2)
        >>> db.list_messages() == [p1]
        True
        >>> db.read_message(p1) == data
        True

        >>> db.clear_message(p1)
        >>> db.list_messages() == []
        True
        >>> db.read_message(p1)
        Traceback (most recent call last):
            ...
        LookupError: No such message.

        >>> db.close()
        """
        pass

    #
    # Signing policy
    #

    def add_signing_policy(self, iid, who, pattern, roles=None,
                           identity=None, **kwargs):
        """Create a policy allowing certain people to write to this dataset."""
        if roles is not None:
            assert roles, 'List of authorized roles must not be empty.'
            kwargs['roles'] = roles

        key = self._create_signing_policy_key(who, pattern)
        self.put(iid, key, kwargs, identity=identity)

    def clear_signing_policy(self, iid, who, pattern, identity=None):
        """Cancel a policy allowing certain people to write to this dataset."""
        key = self._create_signing_policy_key(who, pattern)
        self.delete(iid, key, identity=identity)

    def get_signing_policy(self, iid, who, pattern):
        key = self._create_signing_policy_key(who, pattern)
        return self.get_json(iid, key)

    def _create_signing_policy_key(self, who, pattern):
        assert who == '*' or who == '!' or is_canonical_iid(who)
        return ['policy', 'sign', str(who)] + path_to_list(pattern)

    def _test_manage_signing_policy(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> g = db.create_group()
        >>> iid = db.create_dataset()

        >>> db.add_signing_policy(iid, g, '/posts', roles=['author'])
        >>> db.add_signing_policy(iid, g, '/comments')

        >>> db.get_signing_policy(iid, g, '/posts')
        {u'roles': [u'author']}
        >>> db.get_signing_policy(iid, g, '/comments')
        {}

        >>> db.clear_signing_policy(iid, g, '/comments')
        >>> db.get_signing_policy(iid, g, '/comments') is None
        True

        >>> db.close()
        """
        pass

    #
    # Parse path
    #

    def parse_path(self, path, identity=None):
        if isinstance(path, list):
            return path

        key = path_to_list(path)
        if '!' not in key:
            return key

        if identity:
            iid = hexlify(create_root_item(identity).iid)
        else:
            iid = self.get_my_iid()

        return [(iid if part == '!' else part) for part in key]

    def _test_parse_path(self):
        """
        >>> db = DB()
        >>> db.parse_path(['first', '!', 'last'])
        ['first', '!', 'last']
        >>> db.parse_path('/foo/bar')
        ['foo', 'bar']
        >>> p = db.init_persona(_identity=identity1)
        >>> db.parse_path('/first/!/last') == ['first', p, 'last']
        True
        >>> db.close()
        """
        self

    #
    # Application data access
    #

    def get(self, iid, path, type=None, cipher=None, default=None):
        """Return the value corresponding to a path in the dataset."""
        assert type in (None, 'text', 'json', 'size')
        if type == 'size':
            return self.get_size(iid, path) # size of ciphertext

        iid = hex_to_buffer(iid)
        key = self.parse_path(path)
        c = self.execute("select value from items"
                         " where iid = ? and key = ?"
                         " order by num desc",
                         (iid, buffer(encode(key))))
        try:
            v = get_single_value(c)
            if v is None:
                return default
            v = str(v)
        except LookupError:
            return default

        if cipher:
            v = cipher.decrypt(v)

        if type == 'text':
            return decode_text(v)
        elif type == 'json':
            return parse_json_object(v)
        else:
            return v

    def get_text(self, iid, path, cipher=None):
        """Return a value as Unicode text."""
        return self.get(iid, path, type='text', cipher=cipher)

    def get_json(self, iid, path, cipher=None):
        """Return a JSON value as a dictionary."""
        return self.get(iid, path, type='json', cipher=cipher)

    def get_size(self, iid, path):
        """Return the size of a value without reading the data itself."""
        iid = hex_to_buffer(iid)
        key = self.parse_path(path)
        c = self.execute("select size from items"
                         " where iid = ? and key = ?"
                         " order by num desc",
                         (iid, buffer(encode(key))))
        try:
            size = get_single_value(c)
            if size is not None:
                return size
            raise KeyError
        except LookupError:
            raise KeyError

    def put(self, iid, path, value, cipher=None,
            identity=None, identity2=None):
        """Store or update a value in the dataset."""
        iid = hex(iid)

        if isinstance(value, str):
            pass
        elif isinstance(value, unicode):
            value = value.encode('utf-8')
        elif isinstance(value, dict):
            value = json.dumps(value, sort_keys=True)
        else:
            assert value is None

        with self.read_transaction():
            identity = identity or self.get_private_key()
            key = self.parse_path(path, identity=identity)
            existing_item = self.get_item(iid, key)

        old_value = existing_item.value if existing_item else None
        if value is None or old_value is None or not cipher:
            different = (old_value != value)
        else:
            try:
                different = (cipher.decrypt(old_value) != value)
            except ValueError:
                different = True # Failed to decrypt old value.

        if different:
            if cipher and value is not None:
                value = cipher.encrypt(value)
            seq = existing_item.seq + 1 if existing_item else 1
            item = create_kv_item(iid, key, value, seq, identity)
            if identity2:
                item.countersign(identity2)
            self.put_item(item)
        elif not self.have_root_item(iid):
            raise Unauthorized('No root.')

    def delete(self, iid, path, identity=None, identity2=None):
        """Create a tombstone for a path in the dataset."""
        self.put(iid, path, None, identity=identity, identity2=identity2)

    def get_view(self, iid, base_path='', type=None, cipher=None):
        """Return a dictionary providing a live view into the dataset."""
        return View(self, iid, base_path, type, cipher)

    def _test_get(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> iid = db.create_dataset()

        >>> db.put(iid, '/data/color', 'red')
        >>> db.put(iid, '/data/color', 'green')
        >>> db.get(iid, '/data/color')
        'green'
        >>> db.get(iid, '/data/color', type='size')
        5
        >>> db.delete(iid, '/data/color')
        >>> db.get(iid, '/data/color')
        >>> db.get(iid, '/data/color', type='size')
        Traceback (most recent call last):
            ...
        KeyError
        >>> db.get(iid, '/undefined')
        >>> db.get(iid, '/undefined', type='size')
        Traceback (most recent call last):
            ...
        KeyError

        >>> db.put(iid, '/data/color', 'green')
        >>> db.get_text(iid, '/data/color') == u'green'
        True
        >>> db.put(iid, '/data/color', 'vihre\xc3\xa4')
        >>> db.get_text(iid, '/data/color') == u'vihre\xe4'
        True
        >>> db.put(iid, '/data/color', '\xff')
        >>> db.get_text(iid, '/data/color') == u''
        True

        >>> db.put(iid, 'test', {'answer': 42})
        >>> db.get_json(iid, 'test')
        {u'answer': 42}
        >>> db.put(iid, 'test', '42')
        >>> db.get_json(iid, 'test')
        {}
        >>> db.put(iid, 'test', '{')
        >>> db.get_json(iid, 'test')
        {}

        >>> db.close()
        """
        pass

    def _test_put(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> iid = db.create_dataset()

        >>> db.put(iid, '/data/text', u'testing...')
        >>> db.get(iid, '/data/text')
        'testing...'

        >>> db.put(iid, '/data/json', {'numbers': [1, 2, 3]})
        >>> db.get(iid, '/data/json')
        '{"numbers": [1, 2, 3]}'

        >>> db.put('1234abcd' * 5, '/hunos', None)
        Traceback (most recent call last):
            ...
        Unauthorized: No root.

        >>> db.put(iid, 'dropbox/greeting', 'Hello!', identity=identity2)
        Traceback (most recent call last):
            ...
        Unauthorized
        >>> db.add_signing_policy(iid, '*', '/dropbox/*')
        >>> db.put(iid, 'dropbox/greeting', 'Hello!', identity=identity2)
        >>> db.get(iid, 'dropbox/greeting')
        'Hello!'

        >>> db.put(iid, 'new', None)
        >>> db.get_item(iid, 'new')
        >>> db.put(iid, 'new', 'something')
        >>> db.get_item(iid, 'new').seq
        1
        >>> db.put(iid, 'new', 'something')
        >>> db.put(iid, 'new', None)
        >>> db.delete(iid, 'new')
        >>> db.get_item(iid, 'new').seq
        2

        >>> db.put(iid, '/safe_dropbox/!/msg.txt', 'Hi!', identity=identity2)
        Traceback (most recent call last):
            ...
        Unauthorized
        >>> db.add_signing_policy(iid, '*', '/safe_dropbox/!/*')
        >>> db.put(iid, '/safe_dropbox/!/msg.txt', 'Hi!', identity=identity2)
        >>> path = db.parse_path('/safe_dropbox/!/msg.txt', identity=identity2)
        >>> db.get(iid, path)
        'Hi!'

        >>> db.delete(iid, '/safe_dropbox/!/msg.txt', identity=identity2)
        >>> db.get(iid, path)

        >>> db.close()
        """
        pass

    def _test_get_view(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> iid = db.create_dataset()

        >>> v = db.get_view(iid)
        >>> vv = db.get_view(iid, '/more')
        >>> vv_json = db.get_view(iid, '/more', type='json')
        >>> vv_text = db.get_view(iid, '/more', type='text')

        >>> v['1.txt'] = 'one'
        >>> v['/more/2.txt'] = 'two'
        >>> vv['34.json'] = {'values': [3, 4]}
        >>> v['/more/finnish/3.txt'] = u'kolme'
        >>> vv['/finnish/4.txt'] = u'nelj\xe4'
        >>> vv['finnish/illegal.txt'] = '\xff'

        >>> v['/1.txt']
        'one'
        >>> vv['2.txt']
        'two'
        >>> v['/more/34.json']
        '{"values": [3, 4]}'

        >>> vv_json['34.json']
        {u'values': [3, 4]}
        >>> vv_json['2.txt']
        {}

        >>> vv_text['finnish/3.txt'] == u'kolme'
        True
        >>> vv_text['finnish/4.txt'] == u'nelj\xe4'
        True
        >>> vv_text['finnish/illegal.txt'] == u''
        True

        >>> del vv['finnish/3.txt']
        >>> del vv['nonexistent'] # In principle, this should raise KeyError.

        >>> 'finnish/3.txt' in vv
        False
        >>> '/finnish/4.txt/' in vv
        True
        >>> 'nonexistent' in vv
        False

        >>> vv.keys()
        [u'2.txt', u'34.json', u'finnish/4.txt', u'finnish/illegal.txt']
        >>> vv.items() == [
        ...     (u'2.txt', 'two'),
        ...     (u'34.json', '{"values": [3, 4]}'),
        ...     (u'finnish/4.txt', 'nelj\xc3\xa4'),
        ...     (u'finnish/illegal.txt', '\xff')]
        True
        >>> vv_json.items() == [
        ...     (u'2.txt', {}),
        ...     (u'34.json', {u'values': [3, 4]}),
        ...     (u'finnish/4.txt', {}),
        ...     (u'finnish/illegal.txt', {})]
        True
        >>> vv_text.items() == [
        ...     (u'2.txt', u'two'),
        ...     (u'34.json', u'{"values": [3, 4]}'),
        ...     (u'finnish/4.txt', u'nelj\xe4'),
        ...     (u'finnish/illegal.txt', u'')]
        True

        >>> v['/more'] = 'not included in vv'
        >>> v['/more/finnish'] = 'included in vv'
        >>> del v['/more/finnish/illegal.txt']
        >>> vv.keys()
        [u'2.txt', u'34.json', u'finnish/4.txt', u'finnish']

        >>> db.close()
        """
        pass

    #
    # JSON manipulation using keyword arguments
    #

    def put_json(self, iid, path, new_info=None,
                 cipher=None, identity=None, **kwargs):
        """Store a JSON object constructed from keyword arguments."""
        if new_info is None:
            new_info = kwargs
        else:
            new_info.update(kwargs)

        return self.put(iid, path, new_info, cipher=cipher, identity=identity)

    def update_json(self, iid, path, new_info=None, cipher=None, **kwargs):
        """Update a JSON object using convenient keyword arguments."""
        if new_info is None:
            new_info = kwargs
        else:
            new_info.update(kwargs)

        with self.write_transaction():
            info = self.get_json(iid, path, cipher=cipher)
            if info is None:
                info = new_info
            else:
                info.update(new_info)

            self.put(iid, path, info, cipher=cipher)

    def _test_json(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> iid = db.create_dataset()

        >>> db.put_json(iid, 'x', {'color': 'red'}, shape='round')
        >>> sorted(db.get_json(iid, 'x').items())
        [(u'color', u'red'), (u'shape', u'round')]
        >>> db.put_json(iid, 'x', color='blue', answer=42)
        >>> sorted(db.get_json(iid, 'x').items())
        [(u'answer', 42), (u'color', u'blue')]

        >>> db.update_json(iid, 'z', {'color': 'red'}, shape='round')
        >>> sorted(db.get_json(iid, 'z').items())
        [(u'color', u'red'), (u'shape', u'round')]
        >>> db.update_json(iid, 'z', color='blue', answer=42)
        >>> sorted(db.get_json(iid, 'z').items())
        [(u'answer', 42), (u'color', u'blue'), (u'shape', u'round')]

        >>> db.close()
        """
        pass

    #
    # Timestamps
    #

    def update_timestamp(self, iid, path='/info/modified', new_info=None,
                         cipher=None, identity=None, **kwargs):
        """Store a JSON object including an ISO timestamp."""
        if new_info is None:
            new_info = kwargs
        else:
            new_info.update(kwargs)

        self.put_json(iid, path, new_info, cipher=cipher, identity=identity,
                      timestamp=get_timestamp(include_microseconds=True))

    def _test_timestamp(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)

        >>> info = db.get_json(p, '/info/modified')
        >>> sorted(info.keys())
        [u'timestamp']
        >>> len(info['timestamp']) == len('yyyy-mm-ddThh:mm:ss.uuuuuu')
        True

        >>> db.update_timestamp(p, comment='Testing...')
        >>> info = db.get_json(p, '/info/modified')
        >>> sorted(info.keys())
        [u'comment', u'timestamp']
        >>> info['comment']
        u'Testing...'

        >>> db.close()
        """
        pass

    #
    # Queries
    #

    def list(self, iid, path_prefix='', last_mark=0):
        """Return a list of relative paths given a base path."""
        key_prefix = self.parse_path(path_prefix)

        query = "select num, key, size from items where iid = ?"
        params = [hex_to_buffer(iid)]

        prefix = ''
        if key_prefix:
            prefix = encode(key_prefix)[:-1]
            query += " and key > ?"
            params += [buffer(prefix)]

        if last_mark:
            query += " and num > ?"
            params += [last_mark]

        query += " order by key asc, num desc"

        results = []
        last_key = None
        with self.read_transaction():
            self.last_mark = self.get_current_mark()
            for num, key, size in self.execute(query, params):
                if key != last_key:
                    last_key = key

                    key = str(key)
                    if not key.startswith(prefix):
                        break           # Skip all the rest.

                    if size is not None or last_mark > 0:
                        result_key = decode(key)[len(key_prefix):]
                        if result_key:
                            results.append((num, result_key))

        results.sort()
        return [list_to_path(key) for (num, key) in results]

    # XXX Consider getting rid of get_last_mark() and providing two
    # versions of list() instead, one of which returns multiple values.

    def get_last_mark(self):
        """Return the database mark value saved by the last call to list()."""
        return self.last_mark

    def get_current_mark(self):
        c = self.execute("select seq from sqlite_sequence"
                         " where name='items'")
        try:
            return get_single_value(c)
        except LookupError:
            return 0

    def _test_listing(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> iid = db.create_dataset()
        >>> iid2 = db.create_dataset()

        >>> db.put(iid, 'one', '1')
        >>> db.put(iid, 'two/alpha', '2a')
        >>> db.put(iid, 'two/beta', '2b')
        >>> db.put(iid, 'two/gamma', '2c')
        >>> db.put(iid, 'three', '3')
        >>> db.put(iid, 'two/beta', '')
        >>> db.delete(iid, 'two/gamma')
        >>> db.put(iid2, 'two/whatever', 'IRRELEVANT')

        >>> for path in db.list(iid):
        ...     print path
        info/title.txt
        info/created
        info/modified
        one
        two/alpha
        three
        two/beta
        >>> db.list(iid, 'two')
        [u'alpha', u'beta']
        >>> db.list(iid, 'nonexistent')
        []

        >>> db.list(iid, 'two', last_mark=0)
        [u'alpha', u'beta']
        >>> last_mark = db.get_last_mark()

        >>> db.put(iid, 'two/gamma', '')
        >>> db.delete(iid, 'two/beta')
        >>> db.put(iid2, 'two/hunos', 'IRRELEVANT')
        >>> db.list(iid, 'two', last_mark=last_mark)
        [u'gamma', u'beta']
        >>> db.list(iid, 'two')
        [u'alpha', u'gamma']

        >>> db.list(iid, 'policy')
        []
        >>> db.add_signing_policy(iid, '*', '/guestbook/...')
        >>> db.add_signing_policy(iid, '*', '/guestbook/...',
        ...               note='just testing...')
        >>> db.list(iid, 'policy/sign/*')
        [u'guestbook/...']
        >>> db.clear_signing_policy(iid, '*', '/guestbook/...')
        >>> db.list(iid, 'policy/sign/*')
        []

        >>> db.close()
        """
        pass

    def _test_current_mark(self):
        """
        >>> db = DB()
        >>> db.get_current_mark()
        0
        >>> iid = db.init_persona(_identity=identity1)
        >>> mark = db.get_current_mark()
        >>> db.put(iid, 'test', '')
        >>> db.delete(iid, 'test')
        >>> db.get_current_mark() - mark
        2
        >>> db.close()
        """
        pass

    #
    # Blocking calls
    #

    def blocking_get_dataset_type(self, iid, autosubscribe=True, **options):
        """Return the type of a dataset as soon as the root item arrives."""
        def f(): return self.get_dataset_type(iid)
        def g(): self.subscribe(iid)
        on_first_failure = g if autosubscribe else None
        return poll(f, on_first_failure, **options)

    def blocking_get(self, iid, path, type=None, cipher=None,
                     autosubscribe=True, **options):
        """Return a dataset value as soon as it becomes available."""
        def f(): return self.get(iid, path, type, cipher)
        def g(): self.subscribe(iid)
        on_first_failure = g if autosubscribe else None
        return poll(f, on_first_failure, **options)

    def _test_blocking_calls(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> iid = db.create_dataset()
        >>> db.put(iid, 'answer', '42')

        >>> db.blocking_get_dataset_type(iid)
        u'unspecified'
        >>> db.blocking_get(iid, 'answer')
        '42'
        >>> db.blocking_get(iid, 'nonexistent', block=False)
        >>> db.blocking_get(iid, 'nonexistent', timeout=0.1)
        >>> db.blocking_get(iid, 'nonexistent', timeout=0.1, polling_interval=0.01)

        >>> iid2 = '1234abcd' * 5
        >>> iid3 = '87654321' * 5
        >>> db.list_datasets() == [p, iid]
        True
        >>> db.blocking_get_dataset_type(iid2, block=False)
        >>> db.blocking_get(iid3, 'nonexistent', block=False)
        >>> db.list_datasets() == [p, iid, iid2, iid3]
        True

        >>> db.close()
        """
        pass

    #
    # Raw Item access
    #

    def have_item(self, hash):
        return self.have_kv_item(hash) or self.have_root_item(hash)

    def have_root_item(self, iid):
        return self.get_dataset_type(iid) is not None

    def have_kv_item(self, hash):
        hash = hex_to_buffer(hash)
        c = self.execute("select num from items"
                         " where hash = ?", (hash,))
        try:
            num = get_single_value(c)
            return True
        except LookupError:
            return False

    def get_item_by_hash(self, hash):
        return self.get_kv_item(hash) or self.get_root_item(hash)

    def get_root_item(self, iid):
        iid = hex_to_buffer(iid)
        c = self.execute("select * from datasets"
                         " where iid = ?", (iid,))
        try:
            row = get_single_row(c)
        except LookupError:
            return None

        data = dict(zip(DATASETS_KEYS, row))
        if data['type'] is None:
            return None
        else:
            return root_item_from_sqlite(data)

    def get_kv_item(self, hash):
        hash = hex_to_buffer(hash)
        c = self.execute("select * from items"
                         " where hash = ?", (hash,))
        try:
            row = get_single_row(c)
        except LookupError:
            return None

        data = dict(zip(ITEMS_KEYS, row))
        return kv_item_from_sqlite(data)

    def get_item(self, iid, path):
        iid = hex_to_buffer(iid)
        key = self.parse_path(path)
        c = self.execute("select * from items"
                         " where iid = ? and key = ?"
                         " order by num desc",
                         (iid, buffer(encode(key))))
        try:
            row = get_single_row(c)
        except LookupError:
            return None

        data = dict(zip(ITEMS_KEYS, row))
        return kv_item_from_sqlite(data)

    def put_item(self, item):
        if item.is_root():
            self.put_root_item(item)
        else:
            assert item.is_kv()
            self.put_kv_item(item)

    def put_root_item(self, item):
        with self.write_transaction():
            verify(self, item)
            if not self.have_root_item(item.iid):
                data = item.to_sqlite()
                data['size'] = len(item.encode())
                self.operate("update datasets set type = :type,"
                             " salt = :salt,"
                             " sig = :sig,"
                             " pk = :pk,"
                             " size = :size"
                             " where iid = :iid", data)

    def put_kv_item(self, item):
        with self.write_transaction():
            verify(self, item)

            root = self.get_root_item(item.iid)
            item.normalize(root)

            deleted = 0
            iid = item.iid
            key = item.key
            existing_item = self.get_item(iid, key)
            if existing_item is not None:
                if item <= existing_item:
                    return    # Already have this item or a newer one.
                elif not item.is_auth() and not item.is_policy():
                    # Remove older item, unless required for
                    # verification purposes.
                    self.operate("delete from items"
                                 " where num = ?", (existing_item.num,))
                    deleted = len(existing_item.encode())

            data = item.to_sqlite()
            self.operate("insert into items"
                         " values (null, :hash, :iid, :key, :value, :seq,"
                         "         :sig, :pk, :sig2, :pk2, :size)", data)

            inserted = len(item.encode())
            self._update_dataset_size(iid, inserted - deleted)

            depends = _get_dependency(key, iid)
            if depends:
                self.subscribe(depends)

            # XXX The following was added in 3.0.12 (8 May 2009) and
            # could possibly be handled in conjunction with the policy
            # dependencies when older versions are no longer in wide use.
            depends = _get_appiid_dependency(item)
            if depends:
                self.subscribe(depends)

    def _update_dataset_size(self, iid, delta):
        iid = hex_to_buffer(iid)
        c = self.execute("select size from datasets"
                         " where iid = ?", (iid,))
        size = get_single_value(c) + delta
        self.operate("update datasets set size = ?"
                     " where iid = ?", (size, iid))

    def _test_raw_item_access(self):
        """
        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)

        >>> iid = db.create_dataset()
        >>> iid2 = '1234abcd' * 5
        >>> db.subscribe(iid2)
        >>> iid3 = '87654321' * 5

        >>> root = db.get_root_item(iid)
        >>> root.is_root()
        True
        >>> item = db.get_item(iid, '/info/title.txt')
        >>> item.is_kv()
        True

        >>> db.have_item(iid)
        True
        >>> db.have_item(iid2)
        False
        >>> db.have_item(iid3)
        False
        >>> db.have_item(item.hash)
        True

        >>> db.get_item_by_hash(iid) == root
        True
        >>> db.get_item_by_hash(iid2) is None
        True
        >>> db.get_item_by_hash(iid3) is None
        True
        >>> db.get_item_by_hash(item.hash) == item
        True

        >>> db.get_item(iid, 'nonexistent') is None
        True
        >>> db.get_item(iid2, 'nonexistent') is None
        True
        >>> db.get_item(iid3, 'nonexistent') is None
        True

        >>> db2 = DB()
        >>> db2.put_item(root)
        Traceback (most recent call last):
            ...
        Unauthorized: No subscription.
        >>> db2.put_item(item)
        Traceback (most recent call last):
            ...
        Unauthorized: No root.
        >>> db2.subscribe(iid)
        >>> db2.put_item(root)
        >>> db2.put_item(item)

        >>> db2.put_item(root)
        >>> db2.put_item(item)
        >>> db2.get_current_mark()
        1

        >>> db.delete(iid, '/info/title.txt')
        >>> tombstone = db.get_item(iid, '/info/title.txt')
        >>> tombstone.is_kv()
        True
        >>> tombstone.value is None
        True

        >>> db2.put_item(tombstone)
        >>> db2.put_item(item)
        >>> db2.get_current_mark()
        2
        >>> db2.get_item_by_hash(item.hash) is None
        True
        >>> db2.get_item_by_hash(tombstone.hash) == tombstone
        True

        >>> size = db2.get_dataset_info(iid)['size']
        >>> len(root.encode()) + len(tombstone.encode()) == size
        True

        >>> auth_item = db.get_item(p, ['auth', p])
        >>> auth_item.is_auth()
        True
        >>> db.delete(p, ['auth', p])
        >>> auth_tombstone = db.get_item(p, ['auth', p])
        >>> auth_tombstone.is_auth()
        True
        >>> auth_tombstone.value is None
        True

        >>> db.get_item_by_hash(auth_item.hash) == auth_item
        True
        >>> db.get_item_by_hash(auth_tombstone.hash) == auth_tombstone
        True

        >>> db.close()
        """
        pass

    #
    # Sync support
    #

    def gen_sync_agenda(self, iid, last_mark=None, current_mark=None):
        iid = hex(iid)

        if last_mark is None:
            if self.have_root_item(iid):
                yield 0, iid, None
            else:
                return

        query = "select num, hash, key from items where iid = ?"
        params = [hex_to_buffer(iid)]

        if last_mark:
            query += " and num > ?"
            params += [last_mark]

        if current_mark is not None:
            query += " and num <= ?"
            params += [current_mark]

        query += " order by num"

        cursor = self.execute(query, params)
        try:
            for num, hash, key in cursor:
                hash = hexlify(hash)
                key = decode(str(key))
                depends = _get_dependency(key, iid)

                yield num, hash, depends
        finally:
            cursor.close()

    def _test_sync_agenda(self):
        """
        >>> def summarize(mark, agenda):
        ...     return [(0 if num == 0 else num - mark)
        ...             for num, hash, depends in agenda]

        >>> db = DB()
        >>> p = db.init_persona(_identity=identity1)
        >>> mark = db.get_current_mark()
        >>> iid = db.create_dataset()
        >>> summarize(mark, db.gen_sync_agenda(iid))
        [0, 1, 2, 3]

        >>> db.put(iid, 'data/one', '1')
        >>> db.put(iid, 'data/two', '2')
        >>> db.put(iid, 'data/three', '3')
        >>> db.put(iid, 'data/two', '2!')
        >>> db.delete(iid, 'data/three')
        >>> summarize(mark, db.gen_sync_agenda(iid))
        [0, 1, 2, 3, 4, 7, 8]
        >>> summarize(mark, db.gen_sync_agenda(iid, last_mark=0))
        [1, 2, 3, 4, 7, 8]
        >>> start = mark + 1
        >>> stop = db.get_current_mark() - 1
        >>> summarize(mark, db.gen_sync_agenda(iid, start, stop))
        [2, 3, 4, 7]

        >>> all(depends is None for num, hash, depends in db.gen_sync_agenda(p))
        True
        >>> all(depends is None for num, hash, depends in db.gen_sync_agenda(iid))
        True
        >>> db.add_signing_policy(iid, p, '/comments/!/comment.json')
        >>> mark = db.get_current_mark()
        >>> agenda = list(db.gen_sync_agenda(iid, mark - 1, mark))
        >>> len(agenda)
        1
        >>> num, hash, depends = agenda[0]
        >>> num == mark
        True
        >>> len(hash) == 40
        True
        >>> depends == p
        True

        >>> db.close()
        """
        pass

def _get_dependency(key, iid):
    if len(key) >= 3 and key[0] == 'policy' and key[1] == 'sign':
        if key[2] not in ('*', '!', iid):
            return key[2]

    return None

def _get_appiid_dependency(item):
    if item.key == ['info', 'appiid']:
        iid = item.value
        if iid and is_canonical_iid(iid):
            return iid

    return None

if __name__ == '__main__':
    from peerscape import DB    # Invitation stuff needs post_event() method.
    import doctest
    init_doctest()
    doctest.testmod()
